package class11;

import common.ArrayUtils;


/**
 * 机器人从起始位置，固定步数，走到目标位置的方式,有多少种？
 * 机器人走路问题
 * path: [1，2，3，4，5，6，7]
 * robot:   s     t
 * 说明：
 * 初始值：start=2, target=4, N=7, times=4
 * start:起始位置
 * target:目标位置
 * N:总共位置数
 * times: 走的步数
 * 更新：
 */
public class Code06_robotWay3 {
    public static void main(String[] args) {
        int start = 2, target = 6, N = 7, times = 4;
        int res = way3(start, target, N, times);
        System.out.println("res = " + res);
    }

    public static int way3(int start, int target, int N, int times) {
        int[][] dp = new int[N + 1][times + 1];
        // 只有target为1，其他dp[...][0] = 0;
        dp[target][0] = 1;
        // dp
        for (int rest = 1; rest <= times; rest++) { // 列
            // 第一行单独设置
            dp[1][rest] = dp[2][rest - 1];
            // 递推中间值
            for (int cur = 2; cur < N; cur++) { // 行
                dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
            }
            // 最后一行单独设置
            dp[N][rest] = dp[N - 1][rest - 1];
        }
        ArrayUtils.printMatrixArr(dp);
        return dp[start][times];// 最终返回
    }
}
